package cn.rocky.prepare;

/**
 * 687. 最长同值路径
 */
public class longestUnivaluePath {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    int ans = 0;

    public int longestUnivaluePath(TreeNode root) {
        if (root != null) { maxLength(root,root.val);}
        return ans;
    }

    public int maxLength(TreeNode root,int val) {
        if (root == null) {return 0;}
        int l1 = maxLength(root.left, root.val);
        int r1 = maxLength(root.right, root.val);
        ans = ans > l1 + r1 ? ans : l1 + r1;
        return root.val == val ? Math.max(l1, r1) + 1 : 0;
    }
}
